#include <string.h>
#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0

typedef int ElemType;
typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

void CreateList_L(LinkList *L, int n) 
//随机产生n个元素的值，建立带头结点的单链表l
{
    *L = (LinkList) malloc(sizeof(LNode));//创建头结点
    if (*L == NULL) 
    {
        
        printf("Memory allocation failed\n");
        return;
    }
    (*L)->next = NULL;//头结点指针域为空
    {
        for( int i = n; i > 0; --i) 
        {
            LNode *p = (LNode *) malloc(sizeof(LNode));
            if (p == NULL) 
            {
                printf("内存分配失败\n");
                return;
            }
            scanf("%d", &p->data);//输入元素值
            p->next = (*L)->next;//插入到表头
            (*L)->next = p;
        }
    }
}

int ListInsert_L(LinkList *L, int i, ElemType e){
//在单链线性表L中第i个位置之前插入新的元素e
LinkList p = *L;
int j = 0;
while (p && j < i - 1) {
    p = p->next;
    ++j;
}
if (!p || j > i - 1) {
    return ERROR;
}//i值不合法
LinkList s = (LinkList) malloc(sizeof(LNode));
if(!s) {
    return ERROR;
}//存储分配失败
s->data = e;
s->next = p->next;//插入L中 
p->next = s;
return OK;
}

int GetElem_L(LinkList L, int i, ElemType *e)
//用e返回L中第i个元素的值
{
    LinkList p = L->next;//p指向第一个结点
    int j = 1;//j为计数器
    while (p && j < i) {
        p = p->next;
        ++j;
    }
    if (!p || j > i) {
        return ERROR;
    }//第i个元素不存在
    *e = p->data;//取第i个元素的值
    return OK; 
}

int ListDelete_L(LinkList *L, int i, ElemType *e)
//删除单链线性表L的第i个元素，并用e返回其值
{
    LinkList p = *L;
    LinkList q;
    int j = 0;
    while (p->next && j < i - 1) {
        p = p->next;
        ++j;
    }
    if (!(p->next) || j > i - 1) {
        return ERROR;
    }//i值不合法
    q = p->next;//q指向被删除结点
    p->next = q->next;//将q结点从链中断开
    *e = q->data;//保存被删除结点的数据域
    free(q);//释放被删除结点
    return OK;
}

void MergeList_L(LinkList *La, LinkList *Lb, LinkList *Lc)
//已知单链线性表La和Lb的元素按值非递减排列
//归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列
{
    LinkList pa = (*La)->next;//pa指向La的第一个结点
    LinkList pb = (*Lb)->next;//pb指向Lb的第一个结点
    LinkList pc;
    *Lc = pc = *La;//Lc的头结点为La的头结点
    while (pa && pb) {
        if (pa->data <= pb->data) {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        } else {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    pc->next = pa ? pa : pb;//插入剩余段
    free(*Lb);//释放Lb的头结点
}

int main()
{
    LinkList L;
    int n;
    printf("请输入链表长度：");
    scanf("%d", &n);
    CreateList_L(&L, n);
    LNode *p = L->next;
    while (p!= NULL) 
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");

    int i,e;
    printf("请输入插入位置和元素值：");
    scanf("%d %d", &i, &e);
    if (ListInsert_L(&L, i, e))
    {
        printf("插入成功！\n");
}
    else
    {
        printf("插入失败！\n");
    }
    p = L->next;
    while (p!= NULL) 
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
    GetElem_L(L, 3, &e);
    printf("第3个元素的值为：%d\n", e);

    ListDelete_L(&L, 2, &e);
    printf("删除的元素值为：%d\n", e);
    p = L->next;
    while (p!= NULL) 
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");


    return 0;
}
    